package com.study.lintcode.my.code_10;

/**********************************************************************
 * &lt;p&gt;文件名：Example_1.java &lt;/p&gt;
 * &lt;p&gt;文件描述：(https://www.lintcode.com/problem/a-b-problem/)
 * @project_name：LintCode
 * @author zengshunyao
 * @create 2019/1/5 21:56
 * @history
 * @department：政务事业部
 * Copyright ChengDu Funi Cloud Code Technology Development CO.,LTD 2014
 *                    All Rights Reserved.
 */
public class Example_4 {
    /**
     * @param n: An integer
     * @return: the nth prime number as description.
     */
    public int nthUglyNumber(int n) {
        // write your code here
        int num = 1;
        //1,2,3,4,5,6,8,9
        // num = 2^n*3^p*5^q

        //1也是丑数=>2^0*3^0*5^0
        //第n个丑数
        //当n=1   丑数=1
        //你n>1   丑数
        int p2 = 1;
        int p3 = 1;
        int p5 = 1;
        int UglyNumbers[] = new int[8 * 1024];
        //丑数从小标1开始(含)存
        UglyNumbers[0] = 1;
        //第一个丑数
        UglyNumbers[1] = 1;
        int p = 1;
        int num2 = 0;
        int num3 = 0;
        int num5 = 0;
        while (true) {
            //解决 n=1
            if (p == n) {
                return UglyNumbers[p];
            }
            //找出没出现包含因子2的丑数
            while (true) {
                num2 = UglyNumbers[p2] * 2;
                if (num2 <= UglyNumbers[p]) {
                    p2++;
                } else {
                    break;
                }
            }
            //找出没出现包含因子3的丑数
            while (true) {
                num3 = UglyNumbers[p3] * 3;
                if (num3 <= UglyNumbers[p]) {
                    p3++;
                } else {
                    break;
                }
            }
            //找出没出现包含因子5的丑数
            while (true) {
                num5 = UglyNumbers[p5] * 5;
                if (num5 <= UglyNumbers[p]) {
                    p5++;
                } else {
                    break;
                }
            }

            num = Math.min(Math.min(num2, num3), num5);
            if (num2 == num) {
                p2++;
            } else {
                if (num3 == num) {
                    p3++;
                } else {
                    if (num5 == num) {
                        p5++;
                    }
                }
            }

            UglyNumbers[++p] = num;
            if ((p == n) || (p + 1 >= 8 * 1024)) {
                break;
            }
        }
        return UglyNumbers[p];
    }


    public static void main(String[] args) {
        //1->1
        //2->2
        //3->3
        //4->4
        //5->5
        //6->6
        //7->8
        //8->9
        //9->10
        //10->12
        System.out.println(new Example_4().nthUglyNumber(41));
    }
}
